package Demo1;

/**
 * 自己写的
 */
public class AVLTree {
    static class TreeNode {
        public int val;
        public int bf;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    TreeNode root;

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            // 第一次插入，直接就等于就可以了
            root = node;
            return true;
        }
        // 第二次或者以上次数插入
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

        // 到这里parent 到叶子节点了
        if (parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        // 到这里成功插入了
        node.parent = parent;
        cur = node;

        // 接下来调节平衡因子
        while (parent != null) {
            if (parent.left == cur) {
                parent.bf--;
            } else {
                parent.bf++;
            }
            // 判断平衡因子
            if (parent.bf == 0) {
                // 这种情况下我们认为已经平衡了
                break;
            } else if (parent.bf == -1 || parent.bf == 1) {
                // 这种情况下我们还需要向上调整，去判断平衡因子
                cur = parent;
                parent = cur.parent;
            } else {
                // 这里就是 bf == -2 || bf == 2 了 要调整了
                if (parent.bf == 2) {
                    // 右树高了，需要提高右树
                    if (cur.bf == 1) {
                        rotateLeft(parent);
                    } else {
                        // cur.bf == -1
                        rotateRL(parent);
                    }
                } else {
                    // 左树高了，需要提高左树
                    if (cur.bf == -1) {
                        rotateRight(parent);
                    } else {
                        // cur.bf == 1
                        rotateLR(parent);
                    }
                }
                break;
            }
        }
            return true;
        }
        /**
         * 左右双旋
         */
        private void rotateLR (TreeNode parent){
            TreeNode subL = parent.left;
            TreeNode subLR = subL.right;
            int bf = subLR.bf;

            rotateLeft(parent);
            rotateRight(parent.left);


            // 修改平衡因子
            if (bf == -1) {
                parent.bf = 1;
                subL.bf = 0;
                subLR.val = 0;
            } else if (bf == 1) {
                subL.bf = -1;
                parent.bf = 0;
                subLR.bf = 0;
            }
        }
        /**
         * 右左双旋
         */
        private void rotateRL (TreeNode parent){
            TreeNode subR = parent.right;
            TreeNode subRL = subR.left;

            int bf = subRL.bf;
            rotateRight(parent.left);
            rotateLeft(parent);

            if (bf == 1) {
                parent.bf = -1;
                subR.bf = 0;
                subRL.bf = 0;
            } else if (bf == -1) {
                subR.bf = 1;
                parent.bf = 0;
                subRL.bf = 0;
            }
        }

        /**
         * 左单旋
         * @param parent
         */
        private void rotateLeft (TreeNode parent){
            TreeNode subR = parent.right;
            TreeNode subRL = subR.left;

            parent.right = subRL;
            subR.left = parent;

            if (subRL != null) {
                subRL.parent = parent;
            }
            TreeNode pParent = parent.parent;// 记录父类
            parent.parent = subR;

            // 判断父节点的位置
            if (parent == root) {
                root = subR;
                subR.parent = null;
            } else {
                if (pParent.left == parent) {
                    pParent.left = subR;
                } else {
                    // pParent.right == parent
                    pParent.right = subR;
                }
                subR.parent = pParent;
            }
            // 左旋完毕，修改平衡因子
            parent.bf = 0;
            subR.bf = 0;
        }

        /**
         * 右单旋
         * @param parent
         */


        private void rotateRight (TreeNode parent){
            TreeNode subL = parent.left;
            TreeNode subLR = subL.right;

            parent.left = subLR;
            subL.right = parent;
            if(subLR != null) {
                subLR.parent = parent;
            }
            TreeNode pParent = parent.parent;
            parent.parent = subL;
            // 检查当前是否为根节点
            if (parent == root) {
                root = subL;
                root.parent = null;
            } else {
                if (pParent.left == parent) {
                    pParent.left = subL;
                } else {
                    pParent.right = subL;
                }
                subL.parent = pParent;
            }
            subL.bf = 0;
            parent.bf = 0;
        }
        private void inorder(TreeNode root) {
            if(root == null) {
                return;
            }
            inorder(root.left);
            System.out.println(root.val);
            inorder(root.right);
        }
        private int height(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int lHeight = height(root.left);
            int rHeight = height(root.right);
            return lHeight > rHeight ? lHeight + 1:rHeight+1;
        }
        public boolean isBalanced(TreeNode root) {
            if(root == null) {
                return true;
            }
            int lHeight = height(root.left);
            int rHeight = height(root.right);

            if(lHeight-rHeight != root.bf) {
                System.out.println("平衡因子错误 节点为:" + root.val);
                return false;
            }
            return Math.abs(lHeight - rHeight) <= 1
                    && isBalanced(root.left)
                    && isBalanced(root.right);
        }
}
